Co-pending PCT Patent Application Nos. PCT/EP2008/061167 and PCT/EP2008/063647 disclose a Bloom-filter based source routing solution as the forwarding layer for the publish/subscribe-based networking stack.
By way of a summary of what is disclosed in the above-mentioned PCT applications, consider a network with directed links, where each directed link has a fixed-size link identifier, which has a few bits set to one, and the others are zero. When a delivery path (or a tree) is requested, a topology manager entity performs a bitwise OR operation on the corresponding link identifiers. The result, a small Bloom filter called a zFilter, is passed to the source of the path (tree), and upon forwarding, each node checks which of its link identifiers were added to it by simple and bitwise AND operations.
An important performance indicator of the zFilter-based forwarding layer is the forwarding efficiency, i.e. how much bandwidth is wasted because of false deliveries which were caused by false positives in the time of matching the packet header's zFilter to the outgoing link identifiers (or link identities) when making the forwarding decision. (This is a consequence of the property of Bloom filter as a data structure for storing elements in a compact way.) Formally, forwarding efficiency for a specific delivery tree is the number of links added into the zFilter divided by the number of links the packets use.
To increase the performance of forwarding by reducing false positives, the usage of link identities was proposed in above-mentioned PCT/EP2008/063647. In this solution each link has d different link identities, and the topology manager computes d different zFilter-candidates and chooses the one which is expected to perform the best among of all of the candidates (e.g. having the least number of bits set to one, so that lower number of false deliveries is expected).
Further insight can be achieved from a review of the above-mentioned patent applications PCT/EP2008/061167 and PCT/EP2008/063647.
If the number of false deliveries increases, the probability of the appearance of loops also increases. Consider the simple case where the packet is supposed to traverse through links A->B, B->C and finally C->D. Then, if there is a link between nodes C and A, the packet may be sent over that in the case of a false positive. This way, the packet would get into an infinite loop. Furthermore, the number of the identical packets would increase if the looping packets are not discarded early enough.
Some trivial solutions for solving the problem of the looping packets are disclosed in [P. Jokela, A. Zahemszky, C. Esteve, S. Arianfar and P. Nikander, “LIPSIN: Line speed Publish/Subscribe Inter-Networking”, PSIRP technical report, Jan. 11, 2009, published by European Seventh Framework Programme Theme, project Publish-Subscribe Internet Routing Paradigm, Grant agreement no.: 216173] and [P. Jokela, A. Zahemszky, C. Esteve, S. Arianfar and P. Nikander, “LIPSIN: Line speed Publish/Subscribe Inter-Networking”, in SIGCOMM '09, August 2009].
One straightforward way is to introduce a time-to-live (TTL) field in the packet header, which is decremented hop-by-hop as the packet traverses the network. Finally, the packet is discarded when the counter reaches zero. When calculating the delivery tree, the topology manager (who is responsible of zFilter-creation) can always adjust the initial time-to-live value to according to the characteristics of the tree (e.g. to the largest publisher-subscriber distance).
A more advanced loop prevention approach is to cache those Bloom filters which may cause loops later. For this, for each node it is to necessary to know the link identifiers (and link identities) pointing to the node from the neighbors (we call them incoming link identifiers/identities). In this solution, the forwarding node checks whether the packet matches to any of its incoming link identifiers in addition to the actual incoming interface. If the Bloom filter matches to more than one interface, it puts a (zFilter, interface id) entry into its loop prevention cache with the interface it received the packet from. When forwarding packets, the node should check whether the zFilter is already in the cache. If not, than the packet can be safely forwarded (and it should be also added into the cache if needed). If the zFilter is present in the cache, the packet is only forwarded if the packet arrived on the same interface which is present in the corresponding entry; otherwise it is dropped, as it arrived on different interface than expected. i.e. a loop is detected.
The present applicant has appreciated that the earlier-proposed loop prevention techniques are costly with regard to resource usage (either state in the nodes or unnecessary bandwidth consumption).
In the pure TTL-based solution, even if the TTL for each delivery tree is set separately, one is still not able to eliminate the loops totally. For example, those loops that are generated close to the source of the tree will still be traversed multiple times by the packet until the TTL eventually reduced to zero, causing harmful multiplication of the packets and therefore decreasing the forwarding efficiency.
The problem of the cache-based loop prevention approach is the increased number of operations it requires from the forwarding node at per-packet basis. Besides the original forwarding decision the node should always compare the packet header's zFilter with the cache entries before forwarding, which can be time-consuming if the amount of entries is high, and can slow down the speed of packet forwarding by orders of magnitude.
To estimate the performance of these two solutions, simulations were performed, and the number of entries needed per nodes in the caching-based solution and the forwarding efficiency experienced by the two different solutions were measured. Simulations were run for different-sized trees (1 publisher+7 subscribers, 1+15, 1+23, 1+31) in different Rocketfuel reference topologies, but the results for one topology are shown here (AS1221, with 104 nodes and 156 links, meaning 302 link identifiers, all link weights assumed to be one) as the results were not qualitatively different.
FIG. 1 of the accompanying drawings shows the results for forwarding efficiency, where it is clear that the gap between the caching-based and the TTL-based loop prevention is huge and increasing when the size of the trees are increased (by size of the tree we mean the number of interested nodes in the publication). FIG. 2 of the accompanying drawings shows the percentage of zFilters put into the caches among all the different zFilters seen in nodes with different degrees. It can be concluded that at least the high-degree nodes cache unacceptably a lot, and as the size of the trees increase, the entries required are also rapidly increasing.
It is desirable to address these issues which the present applicant has appreciated.